perm filename SEC4.TEX[105,CSD] blob
sn#536189 filedate 1980-09-19 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00007 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \specialbegin{Logical Connectives} \sendindex{Logical Connectives}
C00011 00003 \specialbegin{Design of Iterative Commands} \sendindex{Design} \sendindex{Iterative Commands}
C00025 00004 \specialbegin{Constructing Correct Programs} \sendindex{Correct Programs}
C00028 00005 \specialbegin{Indefinite Iteration} \sendindex{Indefinite Iteration}
C00035 00006 \specialbegin{Program Format} \sendindex{Program Format}
C00041 00007 \specialbegin{More Operators and Functions}
C00055 ENDMK
C⊗;
\specialbegin{Logical Connectives} \sendindex{Logical Connectives}
At times, we want to execute a command only when a combination of
conditions is satisfied. To execute $\Cscr$ only when both $\Escr ↓{1}$ and
$\Etwo$ are true,
we might write
\wuncode{IF $\Escr ↓{1}$ THEN IF $\Escr ↓{2}$ THEN $\Cscr$}
We may more simply write a single conditional command using a condition,
$\Escr ↓{1}$ AND $\Escr ↓{2}$,
which is only true if both $\Escr ↓{1}$ and $\Escr ↓{2}$ are true:
\wuncode{IF $\Escr ↓{1}$ AND $\Escr ↓{2}$ THEN $\Cscr$}
Similarly, to execute $\Cscr$ when either one of $\Escr ↓{1}$ and $\Escr ↓{2}$
(or both) is true, instead of writing
\startcode
IF $\Escr ↓{1}$ THEN $\Cscr$
ELSE IF $\Escr ↓{2}$ THEN $\Cscr$
\endcode
\noindent
we could use the condition $\Escr ↓{1}$ OR $\Escr ↓{2}$, which is true if either (or both) of
$\Escr ↓{1}$ and $\Escr ↓{2}$ is true, to write
\wuncode{IF $\Escr ↓{1}$ OR $\Escr ↓{2}$ THEN $\Cscr $}
The printing command used in drawing the rook moves on the chessboard in the
previous section could be written:
\startcode
IF (R = ROOKROW) AND (C = ROOKCOL) THEN
WRITE('R')
ELSE IF (R = ROOKROW) OR (C = ROOKCOL) THEN
WRITE('*')
ELSE WRITE('.')
\endcode
\noindent
The parentheses in $(\Escr ↓{1})$ {\tt AND} $(\Escr ↓{2})$, or $(\Escr ↓{1})$ {\tt OR} $(\Escr ↓{2})$,
are essential if $\Escr ↓{1}$ and $\Escr ↓{2}$ are more than a single variable or
constant.
Another logical connective is {\tt NOT}; the condition {\tt NOT} $\Escr$
is true if $\Escr$ is false, and false if $\Escr$ is true. To divide I by 2
if it is an even number, one could say
\wuncode{IF NOT ODD(I) THEN I := I DIV 2}
In general, if $\Escr ↓{1}$ and $\Escr ↓{2}$ are {\sl Boolean expressions}
\sendindex{Boolean expressions} (expressions whose values are true or false),
then
\startcode
$\Escr↓1$ AND $\Escr↓2$
$\Escr↓1$ OR $\Escr↓2$
NOT $\Escr↓1$
\endcode
\noindent
are also Boolean expressions. The first is true only when $\alpha ↓{1}$ and $\alpha ↓{2}$ are
both true. The second is false only when $\alpha ↓{1}$ and $\alpha ↓{2}$ are both false. The
third is true only when $\alpha↓1$ is false.
Ambiguous expressions should be fully parenthesized, like
\wuncode{$\Ascr$ OR $((\Bscr)$ AND $(\Cscr))$}
rather than
\wuncode{$(\Ascr)$ OR $(\Bscr)$ AND $(\Cscr)$}
\example
To print the figures illustrated:
\topoutput
*****
* ***
*****
*****
*****
\botoutput
\startcode
FOR R:=1 TO 5 DO
BEGIN
FOR C:=1 TO 5 DO
IF (R=2) AND (C=2) THEN
WRITE(' ')
ELSE WRITE('*');
WRITELN
END
\endcode
\topoutput
*****
* ***
*****
*** *
*****
\botoutput
\startcode
FOR R:=1 TO 5 DO
BEGIN
FOR C:=1 TO 5 DO
IF ((R=2) AND (C=2)) OR ((R=4) AND (C=4)) THEN
WRITE(' ')
ELSE WRITE('*');
WRITELN
END
\endcode
\topoutput
*****
* * *
*****
* * *
*****
\botoutput
\startcode
FOR R:=1 TO 5 DO
BEGIN
FOR C:=1 TO 5 DO
IF ((R=2) OR (R=4)) AND ((C=2) OR (C=4)) THEN
WRITE(' ')
ELSE WRITE('*');
WRITELN
END
\endcode
\exercise
Use logical connectives to write a simpler solution to the
exercise showing the queen on the chessboard.
\endexercise
\exercise
The input file for this program will contain several sequences of numbers
(don't assume they are integers). Each sequence will be preceded by a
number (1 or greater) which is the length of the sequence. Preceding
everything else on the input will be a number (1 or greater) which
is the number of sequnces. In symbols, the input is
$$N\ L↓1\ A↓{1,1}\ A↓{1,2}\ \cdots\ A↓{1,L↓1}\ L↓2\ A↓{2,1}\ \cdots\ A↓{2,L↓2}\ \cdots\ L↓N\ A↓{N,1}\cdots\ A↓{N,L↓N}$$
Your program should find in each sequence $A↓{i,1}\ \cdots\ A↓{i,L↓i}$
the longest consecutive increasing subsequence, and print the first and last
numbers in that increasing subsequence. (In the case of ties, use the earlier
subsequence.)
Example: in the sequence 3 8 7 2 5 6 4 1 9, the longest consecutive
increasing subsequence is 2 5 6, so the program would print 2 and 6.
Use the program on the data below:
\startcode
5
8 82 31 41 59 26 54 2 17
6 13 17 19 23 29 31
10 90 10 20 30 40 5 15 25 35 34
3 68 52 13
5 1066 1984 1776 1865 1929
\endcode
\exercisefont
If you have read ahead in the course notes, you may see that this problem can
be done using arrays. They are not needed; please do the problem without them.
HINT: If you have difficulty getting started, first write a program which
simply finds the largest number in each sequence, and its position in that
sequence.
\endexercise
\rule{
Check your program on extreme values of data. In the case of this exercise,
this means you should check that it works if $N=1$ (a single
sequence), and if $L↓1=1$ (a sequence of length 1). In addition, you should
check that it handles appropriately (error messages, for example) the
forbidden cases $N≤0$ and $L↓i≤0$.}
\specialbegin{Design of Iterative Commands} \sendindex{Design} \sendindex{Iterative Commands}
A certain breeder of rabbits begins with one pair of newborn rabbits.
Each pair of rabbits has its first litter (another pair) after two months,
and another litter of two each month thereafter. At the end of two years,
how many pairs of rabbits will the breeder have?
Let us designate by $f↓{j}$ the number of pairs of rabbits during the j-th
month. We can see that the number of pairs during the j-th month, for {\tt j > 2}, is
the number during the previous month $(f ↓{j-1})$, plus the number of newborn pairs,
which is equal to the number of pairs in existence two months previously
$(f ↓{j-2})$. In brief,
$$f↓{j} = f↓{j-1} + f↓{j-2} \quad (j ≥ 3)$$
The sequence determined by the rule that each number after the second is the
sum of the preceding two, is:
$$\vbox{\halign{$\ctr{#}$\quad⊗$\ctr{#}$\quad⊗$\ctr{#}$\quad⊗$\ctr{#}$\quad⊗$\ctr{#}$\quad%
⊗$\ctr{#}$\quad⊗$\ctr{#}$\quad⊗$\ctr{#}$\quad⊗$\ctr{#}$\quad⊗$\ctr{#}$\quad⊗$\ctr{#}$\cr
f↓{1} ⊗f↓{2} ⊗f↓{3} ⊗f↓{4} ⊗f↓{5} ⊗f↓{6} ⊗f↓{7} ⊗f↓{8} ⊗f↓{9} ⊗f↓{10} ⊗\ldots\cr
1 ⊗1 ⊗2 ⊗3 ⊗5 ⊗8 ⊗13 ⊗21 ⊗34 ⊗55 ⊗\ldots\cr
}}$$%end of halign
\noindent
This is the well-known Fibonacci sequence. \sendindex{Fibonacci sequence}
A program to compute the answer to this problem might be stated:
\startcode
1. Compute and print $f↓{24}$, where $f↓{1}$ = 1, $f↓{2}$ = 1, and
in general, $f↓{j}$ = $f↓{j-1}$ + $f↓{j-2}$.
(Actually, $f↓{24}$ is the number just before two years elapse;
$f↓{25}$ is the number just after.)
\endcode
\noindent
In the absence of any special knowledge which would allow us to get $f↓{24}$
without first computing $f↓{1}$, $f↓{2}$, $f↓{3}$, $f↓{4}$, etc., a natural decomposition
of the problem would be:
\startcode
1.1 Compute in turn $f↓{1}$,$f↓{2}$,$\ldotss$,$f↓{24}$, where $f↓{1}$ = 1,
$f↓{2}$ = 1, and $f↓{j}$ = $f↓{j-1}$ + $f↓{j-2}$.
1.2 Print $f↓{24}$.
\endcode
Step 1.1 cannot yet be expressed as an iteration, because $f↓{1}$ and $f↓{2}$
are determined by different rules than $f↓{3}$,$f↓{4}$,$\ldotss$,$f↓{24}$.
Thus Step 1.1 must first be decomposed as
\startcode
1.1.1 Set $f↓{1}$ = 1 ;
1.1.2 Set $f↓{2}$ = 1 ;
1.1.3 Compute in turn $f↓{3}$,$f↓{4}$,$\ldotss$,$f↓{24}$
where $f↓{i}$ = $f↓{i-1}$ + $f↓{i-2}$.
\endcode
\noindent
Step 1.1.3 now can be expressed iteratively:
\startcode
1.1.3' FOR I:=3 TO 24 DO
Compute $f↓{i}$ by the rule $f↓{i}$ = $f↓{i-1}$ + $f↓{i-2}$
\endcode
However, to express the iterated command in Pascal, we must make
some provision for having retained the values of $f↓{i-2}$
and $f↓{i-1}$ from previous computations as the values of storage variables.
Suppose at a certain stage of the iteration, say {\tt I} = 8, that {\tt A}
contains 8 (= $f↓{6}$) and {\tt B} contains 13 (= $f↓{7}$). By the command
\wuncode{C := A+B}
we add 8 + 13 = 21 = $f↓{8}$, leaving it in {\tt C}.
To make the analogous action happen at stage {\tt I} = 9 of the iteration,
we must start it off with {\tt A} = 13, and {\tt B} = 21. So we add two more commands
to the iterated block
\startcode
A:=B;
B:=C
\endcode
\noindent
which, when {\tt I}=8, changes {\tt A} to 13 and then {\tt B} to 21, leaving these
variables with the values expected by the next stage of the iteration.
It remains to make {\tt A} = 1 = $f↓{1}$ and {\tt B} = 1 = $f↓{2}$
before entering the
iteration. After the iteration, {\tt C} will contain $f↓{24}$.
We approach such problems by the following procedure:
\bitem Identify the needed information.
At the $i↑{th}$ iteration we need $f↓{i-2}$ and $f↓{i-1}$
to compute $f↓{i}$.
\bitem Choose storage variables in which the information is to be systematically
kept at the beginning of each iteration:
We will find $f↓{i-2}$ in {\tt A} and $f↓{i-1}$ in {\tt B}.
\bitem Assuming that the storage variables hold the desired information from
previous computations, design the process for a typical iteration.
To compute $f↓{i}$, we need $f↓{i-2} + f↓{i-1}$, i.e., {\tt A+B}.
\bitem Determine what information must be retained for the next iteration.
At the next iteration, {\tt I} will have been increased by 1, so we
must have $f↓{(i+1)-2} = f↓{i-1}$ in {\tt A} and
$f↓{(i+1)-1} = f↓{i}$ in {\tt B}.
Let us suppose that at the start of a certain iteration the program
variable {\tt A} contains the number $x$ (= $f↓{i-2}$)
and {\tt B} contains the number
$y$ (= $f↓{i-1}$). At the beginning of the next iteration (i.e., the end of the
current one), {\tt A} must contain $f↓{i-1} = y$, and {\tt B} must contain
$f↓{i} = f↓{i-2} + f↓{i-1} = x + y$. Diagramatically, we have
\threecolalign{
⊗{\tt A}⊗{\tt B}\cr
Initial situation⊗$x$⊗$y$\cr
Desired situation⊗$y$⊗$x + y$\cr
}%end of threecolalign.
\noindent
We now look for a systematic way of changing the initial situation into the
desired situation. Unfortunately the obvious ways of changing the initial
situation into the desired situation fail. If we write
\wuncode{A:=B}
the intial situation will be changed to
\threecolalign{
⊗{\tt A}⊗{\tt B}\cr
New situation⊗$y$⊗$y$\cr
}%end of threecolalign
\noindent
so that the value of $f↓{i-2} (= x)$ has been lost; it is no longer the value of
any variable, but is still needed to compute $f↓{i} (= x + y)$.
On the other hand, if we write
\wuncode{B := A+B}
we reach
\threecolalign{
⊗{\tt A}⊗{\tt B}\cr
New situation⊗$x$⊗$y + y$\cr
}%end of threecolalign
\noindent
and the value of $f↓{i-1} (= y)$ has been lost.
We see that the source of the difficulty is that the old value of {\tt A} is
needed to compute the desired value of {\tt B}, and vice versa; whichever of {\tt }A
and {\tt B} we change first, we lose the information needed to compute the
desired value for the other. This is why a third storage variable {\tt C}, was
introduced to hold one of the values safe.
\fourcolalign{
⊗{\tt A}⊗{\tt B}⊗{\tt C}\cr
Initial situation⊗$x$⊗$y$⊗any value\cr
Situation after {\tt C := A+B}⊗$x$⊗$y$⊗$x + y$\cr
Situation after {\tt A := B}⊗$y$⊗$y$⊗$x + y$\cr
Situation after {\tt B := C}⊗$y$⊗$x + y$⊗$x + y$\cr
}%end of fourcolalign
Returning to the process of designing the iteration,
\bitem Determine what values the storage variables must contain at the beginning
of the first execution of the iterated command.
When {\tt I} = 3, we must have initially {\tt A} = $f↓{I-2}$ = $f↓{1}$ = 1 and
{\tt B} = $f↓{I-1}$ = $f↓{2}$ = 1. Thus the iteration must be preceded by {\tt A:=1}
and {\tt B:=1}.
\bitem Determine what information from the last execution of the iterated command
must be retained for use after the iteration is complete.
When {\tt I} = 24, we will end with {\tt A} = $f↓{I-2}$ = $f↓{23}$, and
{\tt B} = {\tt C} = $f↓{I}$ = $f↓{24}$. The needed information after the iteration is
$f↓{24}$, which will be retained as the value of {\tt B} without change to the
program.
\noindent
We may now restate the program in Pascal as
\startcode
VAR A,B,C : INTEGER;
BEGIN
A:=1; (* F(1) *)
B:=1; (* F(2) *)
FOR I:=3 TO 24 DO
BEGIN (* A = F(I-2), B = F(I-1) *)
C := A+B; (* C = F(I) *)
A:=B; (* A = F(I-1) *)
B:=C; (* B = F(I) *)
END;
(* B = F(24) *)
WRITE('F(24)=',B)
END.
\endcode
\exercise
Design a program to compute $f↓{1}$,$f↓{2}$,$\ldotss$,$f↓{24}$ and print $f↓{24}$ in
which two new elements of the sequence are computed by each execution of the
iterated command. This can be done by a simpler program than the one given
above.
\endexercise
\exercise
Design a program to read 100 numbers from a file and print the
two largest.
\endexercise
\sneakhead{Advice}
When a programming problem is too difficult to cope with conceptually, it
is usually most productive to solve a simplified version of the problem first.
The above exercise, for example, can be simplified to the problem of finding
the largest one of the 100 numbers.
\specialbegin{Constructing Correct Programs} \sendindex{Correct Programs}
Anyone who has written several computer programs knows that it is hard to
write a program of more than ten lines free from errors (``bugs''). Furthermore,
it is difficult to locate and remove the errors (``debugging'') in a disorganized
program; effort invested in systematic design of the program is usually repaid
manyfold during the debugging phase. A simple tool for diagnosis of incorrect
programs is printing the name and value of each program and iteration variable,
whenever it changes. This technique is called tracing; its drawback is that it
is unselective, and often prints too much information.
\example
The rabbit program of the previous section can be traced by adding
{\tt WRITELN} commands as follows:
\startcode
A:=1;
B:=1;
WRITELN('At the beginning A=',A,' B=',B);
FOR I:=3 STEP 1 UNTIL 24 DO
BEGIN
C := A+B;
A:=B; B:=C;
WRITELN('Inside the iteration I=',I,' C=',C,
' A=',A,' B=',B);
END;
PRINT('F(24) =',A)
\endcode
The first few lines of output would be (ignoring spacing)
\topoutput
AT THE BEGINNING A= 1 B= 1
INSIDE THE ITERATION I= 3 C= 2 A= 1 B= 2
INSIDE THE ITERATION I= 4 C= 3 A= 2 B= 3
INSIDE THE ITERATION I= 4 C= 5 A= 3 B= 5
.
.
.
\botoutput
\specialbegin{Indefinite Iteration} \sendindex{Indefinite Iteration}
Sometimes we want a program to repeat a certain operation many times, but we
don't know in advance how many. Pascal provides a form of iteration which
continues until the stated condition for continuing is no longer true. If $\Escr$
is the condition for continuing the repetition, and $\Cscr$ is the command to be
repeated, the command to do the repetition is
\wuncode{WHILE $\Escr$ DO $\Cscr$}
For example, we want a a program to add together as many numbers as the user
wants to type; when he has finished, he types a zero as a {\sl sentinel},
\sendindex{sentinel} i.e. a signal that the iteration is complete.
After reading each number, the program must check that the number read was not
zero before continuing the iteration. If {\tt DATUM} contains the number most
recently read from the terminal, the condition for continuing is
{\tt DATUM $≠$ 0}.
The iterated command must add {\tt DATUM} to the sum being computed, and must then
prompt the user and read the next {\tt DATUM} before it ends, so that the next
test of the continuation condition will actualy test the next number typed.
To make it work the first time, we must correctly initialize {\tt DATUM} and
the sum. We get the program:
\startcode
SUM := 0;
WRITELN(TTY,'FIRST DATUM');
BREAK(TTY);
READ(TTY, DATUM);
WHILE DATUM <> 0 DO
BEGIN
WRITELN(TTY, DATUM);
SUM := SUM + DATUM;
WRITELN(TTY, 'NEXT DATUM');
BREAK(TTY);
READ(TTY,DATUM);
END;
WRITELN(TTY);
WRITELN(TTY, 'SUM = ', SUM)
\endcode
We distinguish {\sl definite iteration}, \sendindex{definite iteration} as
represented by
\wuncode {FOR \sendindex{FOR} $\Vscr$:= $\Escr ↓1$ TO $\Escr ↓2$ DO $\Cscr$}
from the {\sl indefinite iteration} \sendindex{indefinite iteration}
\wuncode {WHILE \sendindex{WHILE} $\Escr$ DO $\Cscr$}
Definite iteration is only applicable when the program can determine before
starting the iteration how many times the command must be repeated,
or at least some upper limit which is sure
to be enough. Indefinite iteration can also handle situations where no limit on the number
of repetitions is known in advance. However, indefinite iteration is more
dangerous; a program like
\startcode
I:=1;
WHILE I <> 0 DO I:=I+1
\endcode
\noindent
can go on forever, or until it is stopped by external intervention.
It is easy to write such a program by mistake, too; in the example here, perhaps the
programmer meant to write the letter {\tt O} or the number 10, rather than zero.
\rule{
When writing an indefinite iteration, convince yourself that the iteration
will not go on forever. Unless the reason is completely obvious, explain
it in a comment.
}
In the first example of indefinite iteration, the ``normal'' situation was to continue
the iteration; the ``special'' case was the sentinel which stopped it. In the following example, we
``normally'' omit the iteration entirely, or do it only once, yet it can be done as often as needed.
If in a certain program we want to read in a number between one and ten, we can use
an indefinite iteration to check that the number lies within these limits, and prompt and
read again if it does not:
\startcode
WRITELN(TTY,'ON A SCALE OF 1 TO 10, HOW DO YOU RATE THIS COURSE?');
BREAK(TTY);
READ(TTY, RATING);
WHILE (RATING < 1) OR (RATING >10) DO
BEGIN
WRITELN(TTY, 'I SAID 1 TO 10. AGAIN');
BREAK(TTY);
READ(TTY, RATING);
END;
(remainder of program)
\endcode
Notice that this part of the program will keep repeating until it succeeds,
guaranteeing that when it is done, {\tt RATING} is between 1 and 10.
If we had written
\wuncode{IF (RATING<1) OR (RATING>10) THEN $\ldots$}
the program would correct one mistake, but not check for a second, and the later
parts of the program might be executed with a value of {\tt RATING} outside
the 1 to 10 range.
\specialbegin{Program Format} \sendindex{Program Format}
By the appropriate use of indentation, the structure of a program can be
displayed clearly. Programs should be written so that when someone sees an
iterative clause, he can tell at a glance how much of the program is iterated,
and when he sees a conditional clause, he can tell at a glance how much of the
program is skipped when the condition is false. We recommend a form in which
the iterative command is written with the iterative clause on one line, and the
iterated command on one or more subsequent lines, indented by perhaps three
spaces more than the iterative clause, thus:
\startcode
S:=0;
FOR I:=1 TO N DO
BEGIN
S := S + I * I * I;
WRITELN(I,S)
END;
WRITELN('*****')
\endcode
\noindent
If the iterated command is very simple, it may be written on the same line with
the iterative clause:
\wuncode{FOR I:= 1 TO N DO WRITE(1/I)}
For conditional commands, we recommend the form
\startcode
IF $\Escr$ THEN
$\Cscr↓1$
ELSE
$\Cscr↓2$
\endcode
\noindent
where $\Cscr ↓{1}$ and $\Cscr ↓{2}$ are indented more than the {\tt IF} and {\tt ELSE} lines.
If $\Cscr ↓{1}$ and and $\Cscr ↓{2}$ are very simple, they can be written on
the same lines as the conditions:
\startcode
IF $\Escr$ THEN $\Cscr↓1$
ELSE $\Cscr↓2$
\endcode
\noindent
or even
\wuncode{IF $\Escr$ THEN $\Cscr ↓{1}$ ELSE $\Cscr ↓{2}$}
Most of our examples are indented according to these conventions.
The reader will find that when he has to make corrections to his programs
(and he will spend a significant fraction of his programming career doing just
that), he will find it much easier to correct a program written with systematic
use of indentation.
\vfill\eject\sendnotes{FINALCHECK: Explicit eject here.}
For example, to find what the following nonsense program
does:
\startcode
FOR I:= 1 TO 3 DO
BEGIN
WRITE('A');
IF I = 2 THEN
WRITE('B')
ELSE
BEGIN
WRITE('C');
FOR J:= 1 TO 2 DO
WRITE('D')
WRITE('E')
END
END;
WRITE('F');
FOR K:=1 TO 4 DO
IF K <> 3 THEN WRITE('G')
\endcode
\noindent
one starts with the most indented sections, finding in turn the following
equivalences:
\vfill
\samecode{
FOR J:= 1 TO 2 DO⊗WRITE('DD');\cr
\quad WRITE('D')⊗\cr\noalign{\hrule}
⊗\cr
BEGIN⊗WRITE('CDDE')\cr
WRITE('C');⊗\cr
FOR J:=1 TO 2 DO⊗\cr
\quad WRITE('D');⊗\cr
WRITE('E')⊗\cr
END\cr\noalign{\hrule}
⊗\cr
BEGIN⊗IF I = 2 THEN\cr
WRITE('A');⊗\quad WRITE('AB')\cr
IF I = 2 THEN⊗ELSE\cr
\quad WRITE('B')⊗\quad WRITE('ACDDE')\cr
ELSE⊗\cr
\quad BEGIN⊗\cr
\quad WRITE('C');⊗\cr
\quad FOR J:=1 TO 2 DO⊗\cr
\qquad WRITE('D');⊗\cr
\quad WRITE('E');⊗\cr
\quad END⊗\cr
END⊗\cr\noalign{\hrule}
⊗\cr
The entire program⊗WRITE('ACDDEABACDDEFGGG')\cr
}%end samecode
\noindent
In brief, the indented regions are significant units, which can be analyzed
independently. In programming courses, graders and programming consultants
should insist on systematic use of comments and indentation.
\specialbegin{More Operators and Functions}
In addition to the familiar arithmetic operators and functions of
analysis, whose representation in Pascal has already been described, there are
a number of others, less familiar, but of considerable importance in
programming.
\bitem{$\Escr ↓{1}$ {\tt DIV} \sendindex{DIV} $\Escr ↓{2}$, $\Escr ↓{1}$ {\tt MOD} \sendindex{MOD} $\Escr ↓{2}$}
The value of $\Escr ↓{1}$ DIV $\Escr ↓{2}$ is the integer part of the
quotient $\alpha ↓{1}$/$\alpha ↓{2}$, where $\alpha ↓{1}$ and $\alpha ↓{2}$
are integers, discarding any remainder; a typical use is
to find how many objects of length $\alpha ↓{2}$ can fit in a space
$\alpha ↓{1}$. If one cuts up a plank of length {\tt A} and width {\tt B},
into shelves of length {\tt C} and width {\tt D}, the number of shelves
which can be made is computed by the expression {\tt (A DIV C)*(B DIV D)}.
The expression $\Escr↓{1}$ {\tt MOD} $\Escr↓{2}$ designates the
remainder of the division $\alpha ↓{1}$/$\alpha ↓{2}$. For example,
the length of the piece of plank left over in the process described above,
could be computed by the expression {\tt A MOD C}.
%\fakfigure{140}{} % Figure Title goes between ending {}'s.
%Put in Diagram
%\startcode
% 11 DIV 4 = 2 ; 11 MOD 4 = 3
% 58 DIV 16 = 3; 58 MOD 16 = 10
% 3 X 2 = 6
%\endcode
In most usage of {\tt DIV} and {\tt MOD,} $\alpha ↓{1}$ and
$\alpha ↓{2}$ are positive numbers. When they are positive,
$\alpha ↓{1}$ div $\alpha ↓{2}$ is the number of times $\alpha ↓{2}$
could be subtracted from $\alpha ↓{1}$
without getting a negative number, and $\alpha ↓{1}$ {\tt MOD} $\alpha ↓{2}$
is the result of these subtractions.
The {\tt MOD} operator is a periodic function of $\alpha ↓{1}$ (at least,
as long as $\alpha ↓{1}$ is positive); if $\alpha ↓{2}$ is an integer and
does not change, and $\alpha ↓{1}$ goes through
the series of values 0, 1, 2, 3, $\ldotss$, the value of $\alpha ↓{1}$ mod
$\alpha ↓{2}$ becomes successively 0, 1, 2, $\ldotss$,
$\alpha ↓{2}$-1, 0, 1, 2, $\ldotss$, $\alpha ↓{2}$-1, 0, 1, 2, $\ldotss$;
because of this, when we want a certain process carried out periodically
during an iteration, we typically use the {\tt MOD} operator (in the form
{\tt I MOD P}, where {\tt I} is the
iteration variable and {\tt P} is the period) as part of the condition which
determines whether the process is carried out. For example, to print a blank
line after every five lines of a table, one might write
\startcode
FOR I:=1 TO 100 DO
BEGIN
WRITELN(I,SQRT(I));
IF I MOD 5 = 0 THEN
BEGIN
WRITELN
END
END
\endcode
As another example of the use of {\tt DIV} and {\tt MOD,} suppose we want to print a
table of roots with {\tt A} entries, placing {\tt B} of them on each line, with the
last line perhaps partially full; we might decompose the problem in either of
two ways. In the first, we iterate, {\tt A} times, the printing of the square
root, afterwards going on to a new line if the number whose root is taken is
a multiple of {\tt B}, i.e., if {\tt I MOD B = 0}, thus:
\startcode
VAR A, B : INTEGER;
BEGIN
READ(A);
READ(B);
FOR I:=1 TO A DO
BEGIN
WRITE(SQRT(I));
IF I MOD B = 0 THEN WRITELN
END
END.
\endcode
In the second decomposition, we iterate first over the lines of printing,
thus:
\startcode
VAR A, B : INTEGER;
BEGIN
READ(A);
READ(B);
FOR I:=1 TO A DIV B DO BEGIN
Print the I-th full line
END;
Print A MOD B leftovers
END.
\endcode
\noindent
The design of this program is simplified by observing:
\bitem The number of full lines is $F = A\quad \hbox{\tt DIV}\quad B$.
\bitem The number of items on the first $I$ lines $(I ≤ F)$ is $I \times B$.
\bitem The $I↑{th}$ line $(I ≤ F)$ thus contains the square
roots of the numbers from ${(I-1)} \times B+1$ through $I \times B$.
\bitem The line of leftovers contains the square roots of the numbers from
$(F \times B)+1$ through $A$.
The program is then:
\startcode
VAR A, B, F : INTEGER;
BEGIN
READ(A);
READ(B);
F := A DIV B; (* NUMBER OF FULL LINES *)
FOR I:= 1 TO F DO (* I COUNTS LINES *)
BEGIN
FOR J := (I-1)*B+1 TO I*B DO
WRITE(SQRT(J));
WRITELN
END;
FOR J := F*B+1 TO A DO
WRITE(SQRT(J))
END.
\endcode
Observe that in this instance, taking the computation and printing of a
single square root as the iterated command resulted in a simpler program than
using the printing of a line as the iterated unit. Often there are several
ways of looking at the structure of a computational task, and one may be a
simpler description, leading to a simpler program, than another.
\bitem{{\tt ABS}$(\Escr)$} \sendindex{{\tt ABS}}
The absolute value, or magnitude, \sendindex{absolute value}
\sendindex{magnitude} of $\alpha$. The most
important use of this operator is to measure the difference
{\tt ABS}$(\Ascr - \Bscr)$ between two numbers $\Ascr$ and $\Bscr$.
\bitem{{\tt TRUNC}${(\Escr)}$}
The largest integer which does not exceed $\alpha$;
\wuncode{$\alpha$-1 < {\tt TRUNC}$(\alpha)$ <= $\alpha$}
%\fakfigure{200}{} % Figure Title goes between ending {}'s
%
%
\bitem{{\tt ROUND}$(\Escr)$}
The value of $\alpha$, rounded to the nearest integer.
\wuncode{ROUND($\alpha$)-{$1\over2$}$≤ \alpha$ < ROUND($\alpha$)+{$1\over2$}}
For example, {\tt ROUND($\alpha$) }is 2 if $1.5 ≤ \alpha < 2.5$.
If one computes a number {\tt X} which would be an integer except for the effect
of small computational errors, {\tt ROUND(X)} gives the exact integer value.
%\fakfigure{200}{} % Figure Title goes between the ending {}'s.
\example
The British monetary system has undergone a conversion to a decimal
system. Under the old system,
\startcode
{\rm 1 pound = 20 shillings = 240 pence}
{\rm 1 shilling = 12 pence.}
\endcode
\noindent
Under the new system,
\displayline{1 pound = 100 new pence.}
The value of {\tt S} shillings plus {\tt D} pence is
\startcode
{\rm $S/20 + D/240$ pounds, or}
{\rm $100(S/20 + D/240) = 5(S + D/12)$ new pence.}
\endcode
This is not always an integer; to round to the nearest integer, one would
write in Pascal:
\wuncode{P := ROUND(5*(S + D/12))}
To convert in the other direction, given {\tt P} new pence, we would first
find the total number of old pence by
\wuncode{T := ROUND(12 * P/5)}
This can be broken down into shillings and (old) pence by
\startcode
S := T DIV 12;
D := T MOD 12
\endcode
\example
After computing a sales tax exactly (in dollars), one wants to round it
to the nearest hundredth (i.e., cent). If {\tt T} is the exact figure in dollars,
{\tt 100*T} is the exact figure in cents, {\tt ROUND(100*T)} is the rounded figure in
cents, and {\tt ROUND(100*T)/100} is the rounded figure in dollars.
\exercise
One meter is 39.37 inches. One centimeter is 1/100 of a
meter. Write a program to print a conversion table from centimeters to feet
and inches, rounded to the nearest inch. Tabulate from 1 to 100
centimeters. Be careful that the logic of your solution is correct;
30 centimeters, for example, is 11.911 inches, and it is easy to write a
program which mistakenly converts it to 0 feet 12 inches, or even
1 foot 12 inches.
\endexercise
\newexercise{The number $\pi$, to ten decimal places, is 3.141592654.
A familiar fractional approximation to $\pi$ is 22/7, or 3.1428, which is
in error by about 0.0012. Find a fraction $\alpha$/$\beta$, where $\beta$
is less than 1000, which is in error by less than 0.0001.
(There is one such fraction which differs from $\pi$ by only about 0.00003.)
}%\endexercise